#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cctype>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<char, int> priority = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};
int flag = 1; // 标志位

// 大数加法
string addStrings(string num1, string num2)
{
    int i = num1.size() - 1, j = num2.size() - 1;
    int tmp = 0;
    string ret;
    while (i >= 0 || j >= 0 || tmp)
    {
        if (i >= 0)
            tmp += num1[i--] - '0';
        if (j >= 0)
            tmp += num2[j--] - '0';
        ret.push_back(tmp % 10 + '0');
        tmp /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

// 大数减法 num1 >= num2
string subStrings(string num1, string num2)
{
    int i = num1.size() - 1, j = num2.size() - 1;
    int tmp = 0;
    string ret;
    while (i >= 0)
    {
        int a = num1[i--] - '0' - tmp;
        int b = j >= 0 ? num2[j--] - '0' : 0;
        if (a < b)
            tmp = 1;
        else
            tmp = 0;
        ret.push_back((a + tmp * 10 - b) % 10 + '0');
    }
    reverse(ret.begin(), ret.end());
    // 去除前导0
    ret.erase(0, ret.find_first_not_of('0'));
    return ret.empty() ? "0" : ret;
}

// 大数乘法
string mulStrings(string num1, string num2)
{
    if (num1 == "0" || num2 == "0")
        return "0";
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    int m = num1.size(), n = num2.size();
    vector<int> tmp(m + n - 1);
    // 相乘再相加
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');

    // 处理进位
    int cur = 0, t = 0;
    string ret;
    while (cur < m + n - 1 || t != 0)
    {
        if (cur < m + n - 1)
            t += tmp[cur++];

        ret += t % 10 + '0';
        t /= 10;
    }
    reverse(ret.begin(), ret.end());
    // 处理前导0
    ret.erase(0, ret.find_first_not_of('0'));
    return ret.empty() ? "0" : ret;
}

// 比较大小 num1 > num2返回1，等于返回0，小于返回-1
int compare(const string &num1, const string &num2)
{
    if (num1.size() != num2.size())
    {
        return num1.size() > num2.size() ? 1 : -1;
    }
    for (int i = 0; i < num1.size(); i++)
    {
        if (num1[i] != num2[i])
        {
            return num1[i] > num2[i] ? 1 : -1;
        }
    }
    return 0;
}

// 大数除法,模拟竖式除法
string divStrings(string num1, string num2)
{
    if (num2 == "0")
    {
        flag = -1; // 除零错误
        return "";
    }
    if (compare(num1, num2) < 0)
    {
        return "0"; 
    }
    if (num2 == "1")
    {
        return num1; 
    }

    string ret;//结果
    string cur;
    for (char digit : num1)
    {
        cur.push_back(digit);
        int q = 0;//每次上的商
        string tmp = num2;
        while (compare(cur, tmp) >= 0)
        {
            tmp = addStrings(tmp, num2);
            q++;
        }
        ret.push_back(q + '0');
        string product = mulStrings(num2, to_string(q));
        cur = subStrings(cur, product);   
    }
    // 去除商的前导0
    ret.erase(0, ret.find_first_not_of('0'));
    return ret.empty() ? "0" : ret;
}

void calculateTop(stack<string> &nums, stack<char> &ops)
{
    if (nums.size() < 2 || ops.empty())
        return;
    string b = nums.top();
    nums.pop();
    string a = nums.top();
    nums.pop();
    char op = ops.top();
    ops.pop();

    if (op == '+')
    {
        nums.push(addStrings(a, b));
    }
    else if (op == '-')
    {
        // 确保a >= b
        if (compare(a, b) < 0)
        {
            flag = -1;
            return;
        }
        nums.push(subStrings(a, b));
    }
    else if (op == '*')
    {
        nums.push(mulStrings(a, b));
    }
    else
    {
        string res = divStrings(a, b);
        if (flag == -1)
            return;
        nums.push(res);
    }
}

string calculate(string &str)
{
    stack<string> nums;
    stack<char> ops;
    string num;
    flag = 1;
    for (int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if (isdigit(c))
        {
            num.push_back(c);
            if (i == str.size() - 1 || !isdigit(str[i + 1]))
            {
                nums.push(num);
                num.clear();
            }
            continue;
        }
        if (c == '+' || c == '-' || c == '*' || c == '/')
        {
            while (!ops.empty() && priority[ops.top()] >= priority[c])
            {
                calculateTop(nums, ops);
                if (flag == -1)
                    return "";
            }
            ops.push(c);
        }
        else if (c == '(')
        {
            ops.push(c);
        }
        else if (c == ')')
        {
            while (!ops.empty() && ops.top() != '(')
            {
                calculateTop(nums, ops);
                if (flag == -1)
                    return "";
            }
            ops.pop();
        }
    }
    while (!ops.empty())
    {
        calculateTop(nums, ops);
        if (flag == -1)
            return "";
    }
    return nums.empty() ? "0" : nums.top();
}

int main()
{
    string str;
    while (1)
    {
        cout << "Calculator> ";
        cin >> str;
        string result = calculate(str);
        if (flag == -1)
        {
            cout << "输入有误，请重新输入" << endl;
        }
        else
        {
            cout << result << endl;
        }
    }
    return 0;
}